package 开发算法.布隆过滤器.BitSet;

import java.util.BitSet;

/**
 * 实现一个布隆过滤器
 */
public class MyBloomFilter {
    // 标记数组（默认大小为2^25=3355万，左移一位，等于乘以2）
    private static final int DEFAULT_SIZE = 2 << 24;
    // 创建多个hash函数（每个函数的随机种子不同）
    private static final int[] SEEDS = new int[]{3, 18, 25, 88, 61, 93};
    // 创建标记位数组
    private BitSet bitSet = new BitSet(DEFAULT_SIZE);
    // hash函数数组
    private SimpleHash[] simpleHashes = new SimpleHash[SEEDS.length];

    /**
     * 构造器
     */
    public MyBloomFilter() {
        //初始化hash数组
        for (int i = 0; i < SEEDS.length; i++) {
            simpleHashes[i] = new SimpleHash(SEEDS.length, SEEDS[i]);
        }
    }

    /**
     * 将一个元素添加到布隆过滤器中
     *
     */
    public void add(Object value) {

        //遍历每一个hash函数，对此元素计算出多个hash值，将标记位数组上每个hash值位置的value设置成true
        for (SimpleHash s : simpleHashes) {
            bitSet.set(s.hash(value), true);
        }
    }

    /**
     * 判断一个元素是否在布隆过滤器中
     *
     * @param value
     * @return 存在则返回true，否则返回false
     */
    public boolean isContain(Object value) {
        boolean res = true;
        //计算全部hash，看看是否全为true
        for (SimpleHash s : simpleHashes) {
            res &= bitSet.get(s.hash(value));
        }
        return res;
    }

    /**
     * 静态内部类，用于实现hash值
     */
    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * hash函数
         *
         * @param value 需要进行hash的值
         * @return
         */
        public int hash(Object value) {
            int h;
            if (value == null) {
                return 0;
            } else {
                return Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
            }
        }
    }
}
